package com.sourcetrip.algorithm.sort.merge;

import com.sourcetrip.algorithm.abs.AbstractCustomedObjectSort;

/**
 * @author: ZhouBert
 * @date: 2020/12/30
 * @description: 十大排序算法之五：归并排序（的对象比较版本） --
 * V0 是一个递归版本，但是可能会有 StackOverFlow 的隐患，所以需要再做一个 迭代版本。
 * --
 * 分析：
 * Merge Sort 是区分于 Bubble, Insertion 的另一种思路。
 * 核心思想是：
 * 1.divide:将全数组分割为一个个小的数组（小序列），直至每个数组只有一个元素；
 * 2.merge:然后将小序列合并为一个个有序序列，直至最后只有一个有序序列。
 * （合并时，是将两个有序序列合并为一个大的有序序列。
 * 如果是一个有序序列 + 一个无序序列：一个个将无序序列中的元素二叉查找到有序序列中，O(nlogn)；
 * 如果是一个有序序列 + 一个有序序列：至少需要一半的额外空间，将序列迁移。O(n),所以已经比上面的时间复杂度更优化了！
 * ）
 * --
 * 时间复杂度和空间复杂度
 * 1.关于时间复杂度：由于存在递归调用，比较难直观看出（或者可以当成树进行处理），可以依托递推公式进行求解。
 * （高中的数学知识，但是一般也不好算，于是可以通过常用递推公式表来进行计算）
 * 2.空间复杂度看PPT
 */
public class MergeCustomedSortV0<E> extends AbstractCustomedObjectSort<E> {

	@Override
	protected void sortArr(E[] objectArr) {
		divide(objectArr, 0, objectArr.length);
	}


	//region	core methods

	/**
	 * 将 objectArr 中的 [begin, end) 的元素进行 divide 操作
	 * 然后做 merge
	 *
	 * @param objectArr
	 * @param begin
	 * @param end
	 */
	private void divide(E[] objectArr, int begin, int end) {
		int size = end - begin;
		if (size < 2) {
			return;
		}

		int mid = ((size) >> 1) + begin;
		divide(objectArr, begin, mid);
		divide(objectArr, mid, end);


		merge(objectArr, begin, mid, end);
	}

	/**
	 * 将两组有序数组合并：
	 * [begin,mid)
	 * [mid,end)
	 * 步骤：
	 * 1.额外开辟一个 left arr 部分的空间；并舍弃原先的 Left
	 * 2.将left 数据 copy 到 arr 中；
	 * 3.进行比较和移动！
	 *
	 * @param objectArr	也可以把 objectArr 抽出来做一个全局变量，可以省去多次创建的步骤，但是仍然需要覆盖数据的步骤！
	 * @param begin
	 * @param mid
	 * @param end
	 */
	private void merge(E[] objectArr, int begin, int mid, int end) {
		int leftSize = mid - begin;
		//额外的一半空间
		E[] leftTemp = (E[]) new Object[leftSize];
		//1.将 left 部分迁移到 leftTemp 上
		System.arraycopy(objectArr, begin, leftTemp, 0, leftSize);
		//设置几个索引
		int lb = 0;
		int rb = mid;
		//当 lb 和 rb 仍有空余
		while (lb < leftSize && rb < end) {
			if (compare(leftTemp[lb], objectArr[rb]) > 0) {
				objectArr[begin] = objectArr[rb++];
			} else {
				objectArr[begin] = leftTemp[lb++];
			}
			begin++;
		}
		//此时 left arr 放置完毕
		if (lb == leftSize) {
			//将剩下的 objectArr 中的放进去，其实就不需要动了！因为本来就在里面！
		}
		if (rb == end) {
			//将 left arr 中的元素覆盖 object arr
			while (lb < leftSize) {
				objectArr[begin++] = leftTemp[lb++];
			}
		}
	}


	//endregion


}
